Learning gene regulatory networks from only positive and unlabeled data.

Dyadic Prediction Using a Latent Feature Log%2DLinear Model

Technical perspective %2D Creativity helps influence prediction precision.

Predicting labels for dyadic data.

Accounting for burstiness in topic models.
Many different topic models have been used successfully for a variety of applications. However, even state-of-the-art topic models suffer from the important flaw that they do not capture the tendency of words to appear in bursts; it is a fundamental property of language that if a word is used once in a document, it is more likely to be used again. We introduce a topic model that uses Dirichlet compound multinomial (DCM) distributions to model this burstiness phenomenon. On both text and non-text datasets, the new model achieves better held-out likelihood than standard latent Dirichlet allocation (LDA). It is straightforward to incorporate the DCM extension into topic models that are more complex than LDA. 1.
The Transporter Classification Database recent advances.
advances
Learning to Find Relevant Biological Articles without Negative Training Examples.
Abstract. Classifiers are traditionally learned using sets of positive and negative training examples. However, often a classifier is required, but for training only an incomplete set of positive examples and a set of unlabeled examples are available. This is the situation, for example, with the Transport Classification Database (TCDB, www.tcdb.org), a repository of information about proteins involved in transmembrane transport. This paper presents and evaluates a method for learning to rank the likely relevance to TCDB of newly published scientific articles, using the articles currently referenced in TCDB as positive training examples. The new method has succeeded in identifying 964 new articles relevant to TCDB in fewer than six months, which is a major practical success. From a general data mining perspective, the contributions of this paper are (i) devising and evaluating two novel approaches that solve the positive-only problem effectively, (ii) applying support vector machines in a state-ofthe-art way for recognizing and ranking relevance, and (iii) deploying a system to update a widely-used, real-world biomedical database. Supplementary information including all data sets are publicly available at www.cs.ucsd.edu/users/knoto/pub/ajcai08. 1
Learning a two%2Dstage SVM%2FCRF sequence classifier.
Learning a sequence classifier means learning to predict a sequence of output tags based on a set of input data items. For example, recognizing that a handwritten word is “cat”, based on three images of handwritten letters and on general knowledge of English letter combinations, is a sequence classification task. This paper describes a new two-stage approach to learning a sequence classifier that is (i) highly accurate, (ii) scalable, and (iii) easy to use in data mining applications. The two-stage approach combines support vector machines (SVMs) and conditional random fields (CRFs). It is (i) highly accurate because it benefits from the maximummargin nature of SVMs and also from the ability of CRFs to model correlations between neighboring output tags. It is (ii) scalable because the input to each SVM is a small training set, and the input to the CRF has a small number of features, namely the SVM outputs. It is (iii) easy to use because it combines existing published software in a straightforward way. In detailed experiments on the task of recognizing handwritten words, we show that the two-stage approach is more accurate, or faster and more scalable, or both, than leading other methods for learning sequence classifiers, including max-margin Markov networks (M3Ns) and standard CRFs.
Learning classifiers from only positive and unlabeled data.
The input to an algorithm that learns a binary classifier normally consists of two sets of examples, where one set consists of positive examples of the concept to be learned, and the other set consists of negative examples. However, it is often the case that the available training data are an incomplete set of positive examples, and a set of unlabeled examples, some of which are positive and some of which are negative. The problem solved in this paper is how to learn a standard binary classifier given a nontraditional training set of this nature. Under the assumption that the labeled examples are selected randomly from the positive examples, we show that a classifier trained on positive and unlabeled examples predicts probabilities that differ by only a constant factor from the true conditional probabilities of being positive. We show how to use this result in two different ways to learn a classifier from a nontraditional training set. We then apply these two new methods to solve a real-world problem: identifying protein records that should be included in an incomplete specialized molecular biology database. Our experiments in this domain show that models trained using the new methods perform better than the current state-of-the-art biased SVM method for learning from positive and unlabeled examples.
Making generative classifiers robust to selection bias.

Finding Transport Proteins in a General Protein Database.
Abstract. The number of specialized databases in molecular biology is growing fast, as is the availability of molecular data. These trends necessitate the development of automatic methods for finding relevant information to include in specialized databases. We show how to use a comprehensive database (SwissProt) as a source of new entries for a specialized database (TCDB, the Transport Classification Database). Even carefully constructed keyword-based queries perform poorly in determining which SwissProt records are relevant to TCDB; we show that a machine learning approach performs well. We describe a maximum-entropy classifier, trained on SwissProt records, that achieves high precision and recall in cross-validation experiments. This classifier has been deployed as part of a pipeline for updating TCDB that allows a human expert to examine only about 2 % of SwissProt records for potential inclusion in TCDB. The methods we describe are flexible and general, so they can be applied easily to other specialized databases. 1
KDD Cup and workshop 2007.
In October, 2006 Netflix released a dataset containing 100 million anonymous movie ratings and challenged the data mining, machine learning and computer science communities to develop systems that could beat the accuracy of its recommendation system, Cinematch. We briefly describe the challenge itself, review related work and efforts, and summarize visible progress to date. Other potential uses of the data are outlined, including its application to the KDD Cup 2007.
KDD Cup and workshop 2007.
In October, 2006 Netflix released a dataset containing 100 million anonymous movie ratings and challenged the data mining, machine learning and computer science communities to develop systems that could beat the accuracy of its recommendation system, Cinematch. We briefly describe the challenge itself, review related work and efforts, and summarize visible progress to date. Other potential uses of the data are outlined, including its application to the KDD Cup 2007.
Clustering documents with an exponential%2Dfamily approximation of the Dirichlet compound multinomial distribution.
The Dirichlet compound multinomial (DCM) distribution, also called the multivariate Polya distribution, is a model for text documents that takes into account burstiness: the fact that if a word occurs once in a document, it is likely to occur repeatedly. We derive a new family of distributions that are approximations to DCM distributions and constitute an exponential family, unlike DCM distributions. We use these so-called EDCM distributions to obtain insights into the properties of DCM distributions, and then derive an algorithm for EDCM maximum-likelihood training that is many times faster than the corresponding method for DCM distributions. Next, we investigate expectationmaximization with EDCM components and deterministic annealing as a new clustering algorithm for documents. Experiments show that the new algorithm is competitive with the best methods in the literature, and superior from the point of view of finding models with low perplexity. 1.
Modeling word burstiness using the Dirichlet distribution.
Multinomial distributions are often used to model text documents. However, they do not capture well the phenomenon that words in a document tend to appear in bursts: if a word appears once, it is more likely to appear again. In this paper, we propose the Dirichlet compound multinomial model (DCM) as an alternative to the multinomial. The DCM model has one additional degree of freedom, which allows it to capture burstiness. We show experimentally that the DCM is substantially better than the multinomial at modeling text data, measured by perplexity. We also show using three standard document collections that the DCM leads to better classification than the multinomial model. DCM performance is comparable to that obtained with multiple heuristic changes to the multinomial model. 1.
Deriving TF%2DIDF as a Fisher Kernel.
Abstract. The Dirichlet compound multinomial (DCM) distribution has recently been shown to be a good model for documents because it captures the phenomenon of word burstiness, unlike standard models such as the multinomial distribution. This paper investigates the DCM Fisher kernel, a function for comparing documents derived from the DCM. We show that the DCM Fisher kernel has components that are similar to the term frequency (TF) and inverse document frequency (IDF) factors of the standard TF-IDF method for representing documents. Experiments show that the DCM Fisher kernel performs better than alternative kernels for nearest-neighbor document classification, but that the TF-IDF representation still performs best. 1
Fast Recognition of Musical Genres Using RBF Networks.

A Bayesian network framework for reject inference.

Sources of Success for Boosted Wrapper Induction.
In this paper, we examine an important recent rule-based information extraction (IE) technique named Boosted Wrapper Induction (BWI) by conducting experiments on a wider variety of tasks than previously studied, including tasks using several collections of natural text documents. We investigate systematically how each algorithmic component of BWI, in particular boosting, contributes to its success. We show that the benefit of boosting arises from the ability to reweight examples to learn specific rules (resulting in high precision) combined with the ability to continue learning rules after all positive examples have been covered (resulting in high recall). As a quantitative indicator of the regularity of an extraction task, we propose a new measure that we call the SWI ratio. We show that this measure is a good predictor of IE success and a useful tool for analyzing IE tasks. Based on these results, we analyze the strengths and limitations of BWI. Specifically, we explain limitations in the information made available, and in the representations used. We also investigate the consequences of the fact that confidence values returned during extraction are not true probabilities. Next, we investigate the benefits of including grammatical and semantic information for natural text documents, as well as parse tree and attribute-value information for XML and
Learning Rules to Improve a Machine Translation System.
Abstract. In this paper we show how to learn rules to improve the performance of a machine translation system. Given a system consisting of two translation functions (one from language A to language B and one from B to A), training text is translated from A to B and back again to A. Using these two translations, differences in knowledge between the two translation functions are identified, and rules are learned to improve the functions. Context-independent rules are learned where the information suggests only a single possible translation for a word. When there are multiple alternate translations for a word, a likelihood ratio test is used to identify words that co-occur with each case significantly. These words are then used as context in context-dependent rules. Applied on the Pan American Health Organization corpus of 20,084 sentences, the learned rules improve the understandability of the translation produced by the SDL International engine on 78 % of sentences, with high precision. 1
Using the Triangle Inequality to Accelerate k%2DMeans.
The k-means algorithm is by far the most widely used method for discovering clusters in data. We show how to accelerate it dramatically, while still always computing exactly the same result as the standard algorithm. The accelerated algorithm avoids unnecessary distance calculations by applying the triangle inequality in two different ways, and by keeping track of lower and upper bounds for distances between points and centers. Experiments show that the new algorithm is effective for datasets with up to 1000 dimensions, and becomes more and more effective as the number k of clusters increases. For k&gt;=20 it is many times faster than the best previously known accelerated k-means method.
Principled Methods for Advising Reinforcement Learning Agents.
An important issue in reinforcement learning is how to incorporate expert knowledge in a principled manner, especially as we scale up to real-world tasks. In this paper, we present a method for incorporating arbitrary advice into the reward structure of a reinforcement learning agent without altering the optimal policy. This method extends the potentialbased shaping method proposed by Ng et al.
Learning the k in k%2Dmeans.
When clustering a dataset, the right number k of clusters to use is often  not obvious, and choosing k automatically is a hard algorithmic problem.
Alternatives to the k%2Dmeans algorithm that find better clusterings.
We investigate here the behavior of the  standard k-means clustering algorithm  and several alternatives to it: the k-  harmonic means algorithm due to Zhang  and colleagues, fuzzy k-means, Gaussian  expectation-maximization, and two new  variants of k-harmonic means. Our aim is  to  nd which aspects of these algorithms  contribute to  nding good clusterings, as  opposed to converging to a low-quality local  optimum. We describe each algorithm in a  uni  ed framework that introduces separate  cluster membership and data weight functions.
Transforming classifier scores into accurate multiclass probability estimates.
Class membership probability estimates are important for many applications of data mining in which classification outputs are combined with other sources of information for decision-making, such as example-dependent misclassification costs, the outputs of other classifiers, or domain knowledge. Previous calibration methods apply only to two-class problems. Here, we show how to obtain accurate probability estimates for multiclass problems by combining calibrated binary probability estimates. We also propose a new method for obtaining calibrated two-class probability estimates that can be applied to any classifier that produces a ranking of examples. Using naive Bayes and support vector machine classifiers, we give experimental results from a variety of two-class and multiclass domains, including direct marketing, text categorization and digit recognition.
Shared challenges in data mining and computational biology %28abstract of invited talk%29.

Bayesian approaches to failure prediction for disk drives.
Hard disk drive failures are rare but are often costly. The ability to predict failures is important to consumers, drive manufacturers, and computer system manufacturers alike. In this paper we investigate the abilities of two Bayesian methods to predict disk drive failures based on measurements of drive internal conditions. We first view the problem from an anomaly detection stance. We introduce a mixture model of naive Bayes submodels (i.e. clusters) that is trained using expectation-maximization. The second method is a naive Bayes classifier, a supervised learning approach. Both methods are tested on realworld data concerning 1936 drives. The predictive accuracy of both algorithms is far higher than the accuracy of thresholding methods used in the disk drive industry today. 1.
Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers.
Accurate, well-calibrated estimates of class membership probabilities are needed in many supervised learning applications, in particular when a cost-sensitive decision must be made about examples with example-dependent costs. This paper presents simple but successful methods for obtaining calibrated probability estimates from decision tree and naive Bayesian classifiers. Using the large and challenging KDD&#039;98 contest dataset as a testbed, we report the results of a detailed experimental comparison of ten methods, according to four evaluation measures. We conclude that binning succeeds in significantly improving naive Bayesian probability estimates, while for improving decision tree probability estimates, we recommend smoothing by -estimation and a new variant of pruning that we call curtailment.
The Foundations of Cost%2DSensitive Learning.
This paper revisits the problem of optimal learning and decision-making when different misclassification errors incur different penalties. We characterize precisely but intuitively when a cost matrix is reasonable, and we show how to avoid the mistake of defining a cost matrix that is economically incoherent. For the two-class case, we prove a theorem that shows how to change the proportion of negative examples in a training set in order to make optimal cost-sensitive classification decisions using a classifier learned by a standard non-costsensitive learning method. However, we then argue that changing the balance of negative and positive training examples has little effect on the classifiers produced by standard Bayesian and decision tree learning methods. Accordingly, the recommended way of applying one of these methods in a domain with differing misclassification costs is to learn a classifier from the training set as given, and then to compute optimal decisions ...
Learning and making decisions when costs and probabilities are both unknown.
In many machine learning domains, misclassication costs are dierent for dierent examples, in the same way that class membership probabilities are exampledependent. In these domains, both costs and probabilities are unknown for test examples, so both cost estimators and probability estimators must be learned. This paper rst discusses how to make optimal decisions given cost and probability estimates, and then presents decision tree learning methods for obtaining well-calibrated probability estimates. The paper then explains how to obtain unbiased estimators for example-dependent costs, taking into account the diculty that in general, probabilities and costs are not independent random variables, and the training examples for which costs are known are not representative of all examples. The latter problem is called sample selection bias in econometrics. Our solution to it is based on Nobel prize-winning work due to the economist James Heckman. We show that the methods we propose are s...
Paradoxes of fuzzy logic%2C revisited.
This paper is a reply to the article entitled Elkan&#039;s Theoretical Argument, Reconsidered by Prof. Enric Trillas and Prof. Claudi Alsina. I would like to express my thanks to Dr. Piero Bonissone for inviting me to write this paper and for showing me the article by Trillas and Alsina in advance of its publication.  Ever since mathematical studies of fuzziness began with a 1965 paper entitled Fuzzy Sets by Lotfi Zadeh [Zad65], it has been important to distinguish between between fuzzy logic and fuzzy set theory. The theorem in my paper The Paradoxical Success of Fuzzy Logic, as published in 1993 [Elk93] and also as revised in 1994 [Elk94], is a result about standard fuzzy logic. The paper of Trillas and Alsina concerns fuzzy sets, and therefore erroneously states that the theorem is false.  At the start of their Section 2, Trillas and Alsina write:  An equivalent formulation in Fuzzy Logic to what Professor Elkan claimed in references  [8] a
Results of the KDD%2799 Classifier Learning.

KDD%2799 Knowledge Discovery Contest.
Data mining techniques are routinely used by fundraisers to select those prospects from a large pool of candidates who are most likely to make a financial contribution. These techniques often rely on statistical models based on trial performance data. This trial performance data is typically obtained by soliciting a smaller sample of the possible prospect pool. Collecting this trial data involves a cost; therefore the fundraiser is interested in keeping the trial size small while still collecting enough data to build a reliable statistical model that will be used to evaluate the remainder of the prospects. We describe an experimental design approach to optimally choose the trial prospects from an existing large pool of prospects. Prospects are clustered to render the problem practically tractable. We modify the standard D-optimality algorithm to prevent repeated selection of the same prospect cluster, since each prospect can only be solicited at most once. We assess the benefits of this approach on the KDD-98 data set by comparing the performance of the model based on the optimal trial data set with that of a model based on a randomly selected trial data set of equal size.
Scalability for Clustering Algorithms Revisited.
This paper presents a simple new algorithm that performs k-means clustering in one scan of a dataset, while using a buffer for points from the dataset of fixed size. Experiments show that the new method is several times faster than standard k-means, and that it produces clusterings of equal or almost equal quality. The new method is a simplification of an algorithm due to Bradley, Fayyad and Reina that uses several data compression techniques in an attempt to improve speed and clustering quality. Unfortunately, the overhead of these techniques makes the original algorithm several times slower than standard k-means on materialized datasets, even though standard k-means scans a dataset multiple times. Also, lesion studies show that the compression techniques do not improve clustering quality. All results hold for 400 megabyte synthetic datasets and for a dataset created from the real-world data used in the 1998 KDD data mining contest. All algorithm implementations and experiments are designed so that results generalise to datasets of many gigabytes and larger.
MEME%2C MAST%2C and Meta%2DMEME New Tools for Motif Discovery in Protein Sequences.

An Efficient Domain%2DIndependent Algorithm for Detecting Approximately Duplicate Database Records.
Detecting database records that are approximate duplicates, but not exact duplicates, is an important task. Databases may contain duplicate records concerning the same realworld entity because of data entry errors, because of unstandardized abbreviations, or because of differences in the detailed schemas of records from multiple databases, among other reasons. In this paper, we present an efficient algorithm for recognizing clusters of approximately duplicate records. Three key ideas distinguish the algorithm presented. First, a version of the Smith-Waterman algorithm for computing minimum edit-distance is used as a domainindependent method to recognize pairs of approximately duplicate records. Second, the union/find algorithm is used to keep track of clusters of duplicate records incrementally, as pairwise duplicate relationships are discovered. Third, the algorithm uses a priority queue of cluster subsets to respond adaptively to the size and homogeneity of the clusters discovered as...
Meta%2DMEME motif%2Dbased hidden Markov models of protein families.
Motivation: Modeling families of related biological sequences using Hidden Markov models (HMMs), although increasingly widespread, faces at least one major problem: because of the complexity of these mathematical models, they require a relatively large training set in order to accurately characterize a given family. For families in which there are few known sequences, a standard linear HMM contains too many parameters to be trained adequately.  Results: This work attempts to solve that problem by generating smaller HMMs which precisely model only the conserved regions of the family. These HMMs are constructed from motif models generated by the EM algorithm using the MEME software. Because motif-based HMMs have relatively few parameters, they can be trained using smaller data sets. Studies of shortchain alcohol dehydrogenases and 4Fe-4S ferredoxins support the claim that motif-based HMMs exhibit increased sensitivity and selectivity in database searches, especially when training sets co...
LPMEME A Statistical Method for Inductive Logic Programming.

Reasoning about Unknown
Static program analysis techniques cannot know certain values, such as the value of user input or network state, at analysis time. While such unknown values need to be treated as non-deterministic choices made by the program’s execution environment, it is still possible to glean very useful information about how such statically unknown values may or must influence computation. We give a method for integrating such non-deterministic choices with an expressive static analysis. Interestingly, we cannot solve the resulting recursive constraints directly, but we give an exact method for answering all may and must queries. We show experimentally that the resulting solved forms are concise in practice, enabling us to apply the technique to very large programs, including an entire operating system. 1.
The Field Matching Problem Algorithms and Applications.
To combine information from heterogeneous sources, equivalent data in the multiple sources must be identified. This task is the field matching problem. Specifically, the task is to determine whether or not two syntactic values are alternative designations of the same semantic entity. For example the addresses Dept. of Comput. Sci. and Eng., University of California, San Diego, 9500 Gilman Dr. Dept. 0114, La Jolla, CA 92093 and UCSD, Computer Science and Engineering Department, CA 92093-0114 do designate the same department. This paper describes three field matching algorithms, and evaluates their performance on real-world datasets. One proposed method is the well-known Smith-Waterman algorithm for comparing DNA and protein sequences. Several applications of field matching in knowledge discovery are described briefly, including WEBFIND, which is a new software tool that discovers scientific papers published on the worldwide web. WEBFIND uses external information sources to guide its search for authors and papers. Like many other worldwide web tools, WEBFIND needs to solve the field matching problemn in order to navigate between information sources.
Exploratory Analysis of Speedup Learning Data Using Epectation Maximization.

ParaMEME a parallel implementation and a web interface for a DNA and protein motif discovery tool.
Many advanced software tools fail to reach a wide audience because they require specialized hardware,  installation expertise, or an abundance of CPU cycles. The worldwide web offers a new opportunity for  distributing such systems. One such program, MEME, discovers repeated patterns, called motifs, in sets  of DNA or protein sequences. This tool is now available to biologists over the worldwide web, using  an asynchronous, single-program multiple-data version of the program called ParaMEME that runs on  an Intel Paragon XP/S parallel computer at the San Diego Supercomputer Center. ParaMEME scales  gracefully to 64 nodes on the Paragon with efficiencies above 72% for large data sets. The worldwide  web interface to ParaMEME accepts a set of sequences interactively from a user, submits the sequences  to the Paragon for analysis, and e-mails the results back to the user. ParaMEME is available for free  public use at http://www.sdsc.edu/MEME.  Keywords: intelligent system, supercomputer, ...
The Value of Prior Knowledge in Discovering Motifs with MEME.
MEME is a tool for discovering motifs in sets of protein or DNA sequences. This paper describes several extensions to MEME which increase its ability to find motifs in a totally unsupervisedfashion, but which also allow it to benefit when prior knowledge is available. When no background knowledge is asserted, MEME obtains increased robustness from a method for determining motif widths automatically, and from probabilistic models that allow motifs to be absent in some input sequences. On the other hand, MEME can exploit prior knowledgeabout a motif being present in all input sequences, about the length of a motif and whether it is a palindrome, and (using Dirichlet mixtures) about expected patterns in individual motif positions. Extensive experiments are reported which support the claim that MEME benefits from, but does not require, background knowledge. The experiments use seven previously studied DNA and protein sequence families and 75 of the protein families documented in the Prosit...
Unsupervised Learning of Multiple Motifs in Biopolymers Using Expectation Maximization.
. The MEME algorithm extends the expectation maximization (EM) algorithm for identifying motifs in unalignedbiopolymer sequences. The aim of MEME is to discover new motifs in a set of biopolymer sequences where little or nothing is known in advance about any motifs that may be present. MEME innovations expand the range of problems which can be solved using EM and increase the chance of finding good solutions. First, subsequences which actually occur in the biopolymer sequences are used as starting points for the EM algorithm to increase the probability of finding globally optimal motifs. Second, the assumption that each sequence contains exactly one occurrence of the shared motif is removed. This allows multiple appearances of a motif to occur in any sequence and permits the algorithm to ignore sequences with no appearance of the shared motif, increasing its resistance to noisy data. Third, a method for probabilistically erasing shared motifs after they are found is incorporated so tha...
Fitting a Mixture Model By Expectation Maximization To Discover Motifs In Biopolymer.
ABSTRACT: The algorithm described in this paper discovers one or more motifs in a collection of DNA or protein sequences by using the technique of expectation maximization to fit a two-component finite mixture model to the set of sequences. Multiple motifs are found by fitting a two-component finite mixture model to the data, probabilistically erasing the occurrences of the motif thus found, and repeating the process to find successive motifs. The algorithm requires only a set of sequences and a number specifying the width of the motifs as input. It returns a model of each motif and a threshold which together can be used as a Bayes-optimal classifier for searching for occurrences of the motif in other databases. The algorithm estimates how many times each motif occurs in the input dataset and outputs an alignment of the occurrences of the motif. The algorithm is capable of discovering several different motifs with differing numbers of occurrences in a single dataset. Motifs are discovered by treating the set of sequences as though they were created by a stochastic process which can be modelled as a mixture of two densities, one of which generated the occurrences of the motif, and the other the rest of the positions in the sequences. Expectation maximization is used to estimate the parameters of the two densities and the mixing
The Paradoxical Success of Fuzzy Logic.
Applications of fuzzy logic in heuristic control have been highly successful, but which aspects of fuzzy logic are essential to its practical usefulness? This paper shows that an apparently reasonable version of fuzzy logic collapses mathematically to two-valued logic. Moreover, there are few if any published reports of expert systems in real-world use that reason about uncertainty using fuzzy logic. It appears that the limitations of fuzzy logic have not been detrimental in control applications because current fuzzy controllers are far simpler than other knowledge-based systems. In the future, the technical limitations of fuzzy logic can be expected to become important in practice, and work on fuzzy controllers will also encounter several problems of scale already known for other knowledge-based systems. 1
Elkan%27s Reply The Paradoxical Controversy over Fuzzy Logic.


The Paradoxical Success of Fuzzy Logic.
Applications of fuzzy logic in heuristic control have been highly successful, but which aspects of fuzzy logic are essential to its practical usefulness? This paper shows that an apparently reasonable version of fuzzy logic collapses mathematically to two-valued logic. Moreover, there are few if any published reports of expert systems in real-world use that reason about uncertainty using fuzzy logic. It appears that the limitations of fuzzy logic have not been detrimental in control applications because current fuzzy controllers are far simpler than other knowledge-based systems. In the future, the technical limitations of fuzzy logic can be expected to become important in practice, and work on fuzzy controllers will also encounter several problems of scale already known for other knowledge-based systems. 1

D. B. Lenat and R. V. Guha

D. B. Lenat and R. V. Guha



A Critical Look at Experimental Evaluations of EBL.

A Rational Reconstruction of Nonmonotonic Truth Maintenance Systems.
Properties. In Luis Moniz Pereira and Anil Nerode, editors, Logic Programming and Non-Monotonic Reasoning, Proceedings of the Second International Workshop, pages 43--59. Lisbon, MIT Press, July 1993. [Min82] Jack Minker. On indefinite databases and the closed world assumption. In Proceedings of the 6th Conference on Automated Deduction, New York, pages 292--308. Springer, 1982. [Min88a] Jack Minker. Foundations of Deductive Databases. Morgan Kaufmann, 95 First Street, Los Altos, CA 94022, 1st edition, 1988. [Min88b] Jack Minker. Perspectives in deductive Databases. Journal of Logic Programming, 5:33--60, 1988. [Min89] Jack Minker. Toward a Foundation of Disjunctive Logic Programming. In Ewing L. Lusk and Ross A. Overbeek, editors, Proceedings of the North American Conference on Logic Programming, pages 1215--1235. MIT Press, 1989. [Min91] Jack Minker. An Overview of Nonmonotonic Reasoning and Logic Programming. CS-TR 2736, Computer Science Dept., Univ. Maryland, University of Marylan...
Incremental%2C Approximate Planning.
   
Independence of Logic Database Queries and Updates.

A Rational Reconstruction of Nonmonotonic Truth Maintenance Systems.
Properties. In Luis Moniz Pereira and Anil Nerode, editors, Logic Programming and Non-Monotonic Reasoning, Proceedings of the Second International Workshop, pages 43--59. Lisbon, MIT Press, July 1993. [Min82] Jack Minker. On indefinite databases and the closed world assumption. In Proceedings of the 6th Conference on Automated Deduction, New York, pages 292--308. Springer, 1982. [Min88a] Jack Minker. Foundations of Deductive Databases. Morgan Kaufmann, 95 First Street, Los Altos, CA 94022, 1st edition, 1988. [Min88b] Jack Minker. Perspectives in deductive Databases. Journal of Logic Programming, 5:33--60, 1988. [Min89] Jack Minker. Toward a Foundation of Disjunctive Logic Programming. In Ewing L. Lusk and Ross A. Overbeek, editors, Proceedings of the North American Conference on Logic Programming, pages 1215--1235. MIT Press, 1989. [Min91] Jack Minker. An Overview of Nonmonotonic Reasoning and Logic Programming. CS-TR 2736, Computer Science Dept., Univ. Maryland, University of Marylan...
Conspiracy Numbers and Caching for Searching And%2FOr Trees and Theorem%2DProving.
This paper has made several important contributions: 1. We have demonstrated the practical feasibility of a general abductive approach to explanation by successfully building a domain-independent system, Accel, that is general enough to perform both plan recognition and diagnosis, yet efficient enough to be of practical utility. We support this claim by extensively evaluating the system on 50 narrative texts in the plan recognition domain, on 50 real patient cases in the set covering diagnosis domain, and on 10 model-based diagnosis scenarios each on an adder, a temperature controller, and the water balance system of the human kidney. Except for the adder circuit, each of the knowledge bases contains hundreds of Horn-clause rules. 2. We have developed a novel evaluation criterion, explanatory coherence, to evaluate the quality of explanations in the plan recognition domain. We present empirical results indicating that our coherence metric outperforms the simplicity metric in selecting the best explanation in the plan recognition domain. Our coherence-based approach performs as well as the probabilistic approach of plan recognition, but without the need to engineer numerous prior and posterior probabilities. 3. We present empirical evidence showing that caching of previously computed explanations is critical to the efficiency of an abduction algorithm. Specifically, speedup of more than an order of magnitude has been obtained on our test problems. In summary, this paper has demonstrated via an implemented system that general and efficient abduction for the tasks of plan recognition and diagnosis is indeed possible, and the future holds much promise for such a general abductive approach to explanation. 10 Acknowledgments
Conspiracy Numbers and Caching for Searching And%2FOr Trees and Theorem%2DProving.
This paper has made several important contributions: 1. We have demonstrated the practical feasibility of a general abductive approach to explanation by successfully building a domain-independent system, Accel, that is general enough to perform both plan recognition and diagnosis, yet efficient enough to be of practical utility. We support this claim by extensively evaluating the system on 50 narrative texts in the plan recognition domain, on 50 real patient cases in the set covering diagnosis domain, and on 10 model-based diagnosis scenarios each on an adder, a temperature controller, and the water balance system of the human kidney. Except for the adder circuit, each of the knowledge bases contains hundreds of Horn-clause rules. 2. We have developed a novel evaluation criterion, explanatory coherence, to evaluate the quality of explanations in the plan recognition domain. We present empirical results indicating that our coherence metric outperforms the simplicity metric in selecting the best explanation in the plan recognition domain. Our coherence-based approach performs as well as the probabilistic approach of plan recognition, but without the need to engineer numerous prior and posterior probabilities. 3. We present empirical evidence showing that caching of previously computed explanations is critical to the efficiency of an abduction algorithm. Specifically, speedup of more than an order of magnitude has been obtained on our test problems. In summary, this paper has demonstrated via an implemented system that general and efficient abduction for the tasks of plan recognition and diagnosis is indeed possible, and the future holds much promise for such a general abductive approach to explanation. 10 Acknowledgments


Automated Inductive Reasoning about Logic Programs.

A Decision Procedure for Conjunctive Query Disjointness.

Automated Inductive Reasoning about Logic Programs.

